package BinaryTree;

import java.util.Deque;
import java.util.LinkedList;

public class Exercise {
    public static void main(String[] args) {
        //相同的树(oj)
        TreeNode p = new TreeNode('1');
        TreeNode tree2 = new TreeNode('2');
        TreeNode tree3 = new TreeNode('3');
        p.left = tree2;
        p.right = tree3;
        TreeNode q = new TreeNode('1');
        TreeNode tree4 = new TreeNode('2');
        TreeNode tree5 = new TreeNode('3');
        q.left = tree4;
        q.right = tree5;
        boolean flg = isSameTree(p, q);
        System.out.println(flg);

        //另一颗树的子树
        TreeNode root = new TreeNode('3');
        TreeNode t2 = new TreeNode('1');
        TreeNode t3 = new TreeNode('2');
        TreeNode t4 = new TreeNode('4');
        TreeNode t5 = new TreeNode('5');
        root.left = t4;
        root.right = t5;
        t4.left = t2;
        t4.right = t3;
        TreeNode subroot = new TreeNode('4');
        TreeNode t6 = new TreeNode('1');
        TreeNode t7 = new TreeNode('2');
        subroot.left = t6;
        subroot.right = t7;
        boolean flg1 = isSubtree(root, subroot);
        System.out.println(flg1);


        //翻转二叉树
        TreeNode node = invertTree(root);
        new BinaryTree().preOrder(node);
        System.out.println();


        //平衡二叉树
        TreeNode n1 = new TreeNode('1');
        TreeNode n2 = new TreeNode('2');
        TreeNode n3 = new TreeNode('2');
        TreeNode n4 = new TreeNode('3');
        TreeNode n5 = new TreeNode('3');
        TreeNode n6 = new TreeNode('4');
        TreeNode n7 = new TreeNode('4');
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n4.left = n6;
        n4.right = n7;
        System.out.println(isBalanced(n1));


        //对称二叉树
        System.out.println(isSymmetric(n1));
    }

    //时间复杂度:O(min(m,n))
    //其中m和n分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。
    //空间复杂度O(min(m,n))
    //其中m和n分别是两个二叉树的节点数空间复杂度取决于递归调用的层数递归调用的层数不会超过较小的二叉树的最大高度最坏情况下二叉树的高度等于节点数。
    //1.一个为空一个不为空，不是相同的树
    //2.两个都是空，是相同的树
    //3.两个都不为空，不一定是，还要比较val
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
            //走到这里一个为空，一个不为空
        } else if (p == null || q == null) {
            return false;
        }
        // boolean leftflg=isSameTree(p.left,q.left);
        // boolean rightflg=isSameTree(p.right,q.right);
        // if(leftflg&&rightflg) {
        //     if(p.val!=q.val) {
        //         return false;
        //     }else {
        //         return true;
        //     }
        // }
        // return false;
        else if (p.val != q.val) {
            return false;
        }
        //走到这里，p和q都不为空，且值一样
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //时间复杂度：
    //对于每一s上的点，都需要做一次深度优先搜索来与t匹配，匹配一次的时间代价是O(∣t∣)
    //那么总的时间代价就是 O(∣s∣×∣t∣)。故渐进时间复杂度为 O(∣s∣×∣t∣)
    //空间复杂度：
    //假设s 深度:s  t的深度:t，任意时刻栈空间的最大使用代价是O(max{s,t})。故渐进空间复杂度为O(max{s,t})
    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null || subRoot == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        if (isSubtree(root.left, subRoot)) {
            return true;
        }
        if (isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }

    //时间复杂度:O(N) 空间复杂度:O(数的高度)
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {                  //如果根节点为空，那么就翻转不了
            return null;
        }
        //翻转根节点的左右结点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //时间复杂度:O(N^2) 每一个结点都要判断高度 空间复杂度:O(树的高度)
    //有了计算节点高度的函数，即可判断二叉树是否平衡。
    // 具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过1,再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。
    // 这是一个自顶向下的递归的过程。
    public static boolean isBalanced(TreeNode root) {
        //要求:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1 。
        if (root == null) {
            return true;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        //为什么递归左子树的子树和右子树的子树:首先是看到了要求，其次如果一开始的根满足了左子树与右子树的高度差不超过1
        //而左子树的左子树的高度比右子树的高度差大于1，那么就不满足情况
    }

    private static int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }
//方法一由于是自顶向下递归，因此对于同一个节点，函数 height会被重复调用，导致时间复杂度较高。
// 如果使用自底向上的做法，则对于每个节点，函数 height 只会被调用一次。
// 自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。
// 如果一棵子树是平衡的，则返回其高度（高度一定是非负整数）否则返回−1如果存在一棵子树不平衡，则整个二叉树一定不平衡。
//    public static boolean isBalanced(TreeNode root) {
//          return height(root)>=0;         //当root为空时会等于0
//    }
//    private static int height(TreeNode root) {
//        if(root==null) {
//            return 0;
//        }
//        int leftHeight=height(root.left);
//        int rightHeight=height(root.right);
//        //如果已经有一处地方不满足要求了，那么就结束，不在继续往下
//        //leftHeight==-1||rightHeight==-1这个条件作用:如果只有左子树，而左子树返回了-1，那么Math.abs(leftHeight-rightHeight)>1
//        //就会出问题，因为他的结果为1
//        if(leftHeight==-1||rightHeight==-1||Math.abs(leftHeight-rightHeight)>1) {
//            return -1;
//        }else {
//            return Math.max(leftHeight,rightHeight)+1;
//        }
//    }

    //判断整棵树是否为轴对称
    //判断这稞数的左子树和右子树是否对称:左子树的左树和右子树的右树，左子树的右树和右子树的左树
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    public static boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree == null && rightTree != null || rightTree == null && leftTree != null) {
            return false;
        }
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) {
            return null;
        }
        if(root==p||root==q) {
            return root;
        }
        TreeNode leftRet=lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet=lowestCommonAncestor(root.right,p,q);
        if(leftRet != null&& rightRet != null) {
            return root;
        }else if(leftRet!=null) {
            return leftRet;
        }else if(rightRet!=null) {
            return rightRet;
        }
        return null;
    }
    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack) {
        if(root==null||node==null) {
            return false;
        }
        stack.push(root);
        if(root==node) {
            return true;
        }
        boolean ret1=getPath(root.left,node,stack);
        if(ret1) {
            return true;
        }
        boolean ret2=getPath(root.right,node,stack);
        if(ret2) {
            return true;
        }
        stack.pop();
        return false;
     }
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        //1.两个栈当中存好数据
        Deque<TreeNode> stack1=new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2=new LinkedList<>();
        getPath(root,q,stack2);
        //2.判断栈的大小
        int size1=stack1.size();
        int size2=stack2.size();
        if(size1>size2) {
            int size=size1-size2;
            while(size--!=0) {
                stack1.pop();
            }
        }else {
            int size=size2-size1;
            while(size--!=0) {
                stack2.pop();
            }
        }
        while(!stack1.isEmpty()&&!stack2.isEmpty()) {
            if(stack1.peek()!=stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.peek();
            }
        }
        return null;
    }
    //根据前序遍历和中序遍历求整个二叉树
    public int i;
    public TreeNode buildTree(char[] preorder, char[] inorder) {
        //1.根据前序遍历找到根(每一个左右子树都可以看做一个根，在中序遍历中找到他的位置，他的左右就是他的左右子树!)
        //2.在中序遍历中找到根，左边是左树，右边是右树
        return buildTreeChild(preorder,inorder,0,inorder.length-1);

    }
    public TreeNode buildTreeChild(char[] preorder, char[] inorder,int inbegin,int inend) {
        if(inbegin>inend) {         //等于时会有一个结点
            return null;
        }
        TreeNode root=new TreeNode(preorder[i]);
        int rootIndex=findIndex(inorder,inbegin,inend,preorder[i]);
        i++;
        root.left=buildTreeChild(preorder,inorder,inbegin,rootIndex-1);   //左树在中序数组中根结点位置的左边
        root.right=buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;

    }
    public int findIndex(char[] inorder,int inbegin,int inend,int key) {
        for(int i=inbegin;i<=inend;i++) {
            if(inorder[i]==key) {
                return i;
            }
        }
        return -1;
    }
    //根据中序后序遍历求出该二叉树
    public int i1;
    public TreeNode buildTree1(char[] inorder1, char[] postorder) {
        i1=postorder.length-1;
        return buildTreeChild1(inorder1,postorder,0,postorder.length-1);
    }
    public TreeNode buildTreeChild1(char[] inorder1, char[] postorder,int begin,int end) {
        if(begin>end) {
            return null;
        }
        TreeNode root=new TreeNode(postorder[i]);   //后序遍历最后一个为根结点，根的前面是右节点
        int rootIndex=findIndex1(inorder1,begin,end,postorder[i]);   //所以先找到根，在设置他的右子树
        i--;
        root.right=buildTreeChild(inorder1,postorder,rootIndex+1,end);
        root.left=buildTreeChild(inorder1,postorder,begin,rootIndex-1);
        return root;
    }
    public int findIndex1(char[] inorder1,int inbegin,int inend,int key) {
        for(int i=inbegin;i<=inend;i++) {
            if(inorder1[i]==key) {
                return i;
            }
        }
        return -1;
    }
     //root = [1,2,3,4]   "1(2(4))(3)"
    //给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
    //空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
    //提示://左边为空，右边为空，什么都不做
          //左边不为空，右边为空，直接加）
          //左边为空，右边不为空，直接加()
     public String tree2str(TreeNode root) {
         StringBuilder stringBuilder = new StringBuilder();
         tree2strChilde(root,stringBuilder);
         return stringBuilder.toString();
     }
    public void tree2strChilde(TreeNode root,StringBuilder stringBuilder) {
        if(root==null) {
            return;
        }
        stringBuilder.append(root.val);
        if(root.left==null&&root.right==null) {
            return;
        }
        if(root.left!=null) {
            stringBuilder.append('(');
            tree2strChilde(root.left,stringBuilder);
            stringBuilder.append(')');
        }else {                             //通过列子:左树为空的时候，直接加()
            stringBuilder.append("()");
        }
        if(root.right!=null) {
            stringBuilder.append('(');
            tree2strChilde(root.right,stringBuilder);
            stringBuilder.append(')');
        }
    }
}
